import java.util.ArrayList;
import java.util.List;

//描述 https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e?tpId=13&tags=&title=&difficulty=0&judgeStatus=0&rp=0
//        给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
//        注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示
// 注意这里传入的一棵树的其中一个节点，不一定是根节点
public class Solution9 {
    static List<TreeLinkNode> treeLinkNodes = new ArrayList<>();
    //还原然后中序法
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        TreeLinkNode tl = pNode;
        while (tl.next!=null){
            tl = tl.next;//获取到根节点
        }
        //中序遍历 加到数组
        toMid(tl);

        for (int i=0;i<treeLinkNodes.size();i++){
            if (pNode==treeLinkNodes.get(i)){
                //如果当前是最后一个节点则返回null
//                if (i==treeLinkNodes.size()-1){
//                    return null;
//                }
//                return treeLinkNodes.get(i+1);
                return i == treeLinkNodes.size()-1?null:treeLinkNodes.get(i+1);

            }
        }
        return null;

    }
    //直接寻找归纳法
//    仔细观察，可以把中序下一结点归为几种类型：
//    有右子树，下一结点是右子树中的最左结点，例如 B，下一结点是 H
//    无右子树，且结点是该结点父结点的左子树，则下一结点是该结点的父结点，例如 H，下一结点是 E
//    无右子树，且结点是该结点父结点的右子树，则我们一直沿着父结点追朔，直到找到某个结点是其父结点的左子树，
//    如果存在这样的结点，那么这个结点的父结点就是我们要找的下一结点。例如 I，下一结点是 A；例如 G，并没有符合情况的结点，所以 G 没有下一结点
    public TreeLinkNode GetNext1(TreeLinkNode pNode) {
        // 1. 有右子树，下一结点是右子树中的最左结点
        if (pNode.right != null) {
            TreeLinkNode pRight = pNode.right;
            while (pRight.left != null) {
                pRight = pRight.left;
            }
            return pRight;
        }
        // 2. 无右子树，且结点是该结点父结点的左子树，则下一结点是该结点的父结点，例如 H，下一结点是 E
        if (pNode.next != null && pNode.next.left == pNode) {
            return pNode.next;
        }
        // 3.无右子树，且结点是该结点父结点的右子树，则我们一直沿着父结点追朔，直到找到某个结点是其父结点的左子树，
        if (pNode.next != null) {
            TreeLinkNode pNext = pNode.next;
            while (pNext.next != null && pNext.next.right == pNext) {
                pNext = pNext.next;
            }
            return pNext.next;
        }
        return null;
    }
    void toMid(TreeLinkNode pNode){
        if(pNode!=null) {
            toMid(pNode.left);
            treeLinkNodes.add(pNode);
            toMid(pNode.right);
        }
    }
}
